import java.util.Arrays;

public class Class1 {

    /**
     * 每趟要装尽量多的货物
     * 每次要跑尽量少的路程
     * @param productList
     * @param drivingTimes
     * @return
     */
        public static int getMinimumTime (int[] productList, int[][] drivingTimes) {
            // write code here
            //step1 计算要跑多少趟
            Arrays.sort(productList);
            int num_p =0;
            int low = 0;
            int high = productList.length-1;
            while (low<high){
                if (productList[low]+productList[high]>10){
                    high--;
                }else {
                    high--;
                    low++;
                }
                num_p++;
            }
            int n = drivingTimes.length;
            int num = num_p/4 ;
            if (num_p%4!=0){
                num++;
            }
            int min_start = min_len(drivingTimes,0,n-1);
            int min_return = min_len(drivingTimes,n-1,0);
            return min_start*num+min_return*(num-1);

            //step2 计算一次的最短时间
        }

        public static  int min_len(int[][] a,int start,int end){
            int n = a.length;
            int visit[] = new int[n];
            int dist[] = new int[n];
            for (int i=0;i<n;i++){
                dist[i] =  a[start][i];
            }
            visit[start]=1;
            for (int i=0;i<n;i++){
                int min_dist = Integer.MAX_VALUE;
                int middle =1;
                for (int j=0;j<n;j++){
                    if (visit[j]==0&&min_dist>dist[j]){
                        min_dist = dist[j];
                        middle=j;
                    }
                }
                for (int j=0;j<n;j++){
                    if (visit[j]==0&&dist[j]>dist[middle]+a[middle][j]){
                        dist[j] = a[middle][j]+dist[middle];
                    }
                }
                visit[middle] =1;

            }
            return dist[end];
        }

    /**
     * [5, 5, 6, 6, 10, 10, 10],[[0, 1, 5], [1, 0, 2], [5, 1, 0]]
     * @param args
     */
    public static void main(String[] args) {
        int[] p_list = {5, 5, 6, 6, 10, 10, 10};
        int[][] d = {{0, 1, 5},
                {1, 0, 2},
                {5, 1, 0}};
        System.out.println( getMinimumTime(p_list,d));

    }



}
